package cn.hycat.leetcode.middle;

import java.util.*;

/**
 * @author 吕泽浩业
 * @version 1.0
 */
public class L46全排列 {
    private List<List<Integer>> lists = new ArrayList<>();
    private List<Integer> list = new ArrayList();

    public List<List<Integer>> permute(int[] nums) {
        dfs(nums, 0);
        return lists;
    }

    private void dfs(int[] nums, int i) {
        if(nums.length == i) {
            for(int j = 0 ; j < nums.length; j++) {
                list.add(nums[j]);
            }
            lists.add(list);
            return;
        }

        for(int index = i; index < nums.length; index++) {
            swap(nums, i, index);
            dfs(nums, index + 1);
            swap(nums, i, index);
        }
    }

    public void swap(int[] nums, int i, int j ) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
